package problem;

import java.util.HashMap;

public class S_105 {
    //从前序和中序遍历序列构造二叉树

      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }

    class Solution {

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0 || preorder.length != inorder.length) {
                return null;
            }
            return helper(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
        }
        private TreeNode helper(int[] preorder,int pStart,int pEnd,int[] inOrder,int iStart,int iEnd){
            if(pStart>pEnd||iStart>iEnd) return null;
            TreeNode root=new TreeNode(preorder[pStart]);
            int index=0;    //index是根节点在中序遍历中的位置
            while(inOrder[iStart+index]!=preorder[pStart]) index++;
            //重建左子树
            root.left=helper(preorder,pStart+1,pStart+index,inOrder,iStart,iStart+index-1);
            //重建右子树
           root.right = helper(preorder, pStart + index + 1, pEnd, inOrder, iStart + index + 1, iEnd);
           return root;
        }
    }
}
